import java.util.Random;

public class Test03 {

    class Solution {
        /**
         * 方法一：
         * 利用快速排序
         * 原本是将一个数组划分为两个部分进行排序
         * 现在将数组划分为 三个部分解决
         * 基准元素这里进行随机取
         *
         * @param nums
         * @return
         */
        public int[] sortArray(int[] nums) {
            qsort(nums, 0, nums.length - 1);
            return nums;
        }

        public void qsort(int[] nums, int l, int r) {
            if (l >= r) {
                return;
            }
            // 首先选取基准元素
            Random random = new Random();

            int key = nums[random.nextInt(r - l + 1) + l];

            int left = l - 1, right = r + 1, i = l;
            // while循环进行遍历
            while (i < right) {
                if (nums[i] < key) {
                    // 进行交换
                    swap(nums, i++, ++left);
                } else if (nums[i] == key) {
                    i++;
                } else {
                    // 进行交换
                    swap(nums, --right, i);
                }
            }
            qsort(nums, l, left);
            qsort(nums, right, r);

        }

        public void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

}
